/**
 * Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character
 */
package com.xinpan.exercise;

//do again
public class EditDistance {
    public int minDistance(String word1, String word2) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(word1.length() == 0)
            return word2.length();
        else if(word2.length() == 0)
            return word1.length();
            
        if(word1.charAt(0) == word2.charAt(0))
            return minDist(word1, word2, 1, 1, 0);
        
        int del = minDist(word1, word2, 1, 0, 1);
        int rep = minDist(word1, word2, 1, 1, 1);
        int ins = minDist(word1, word2, 0, 1, 1);
        
        int min = del < rep ? del : rep;
        min = ins < min ? ins : min;
        return min;
    }
    
    public int minDist(String w1, String w2, int s1, int s2, int dist)
    {
        if(w1.length() == s1)
            return dist + w2.length() - s2;
        else if(w2.length() == s2)
            return dist + w1.length() - s1;
            
        if(w1.charAt(s1) == w2.charAt(s2))
            return minDist(w1, w2, s1+1, s2+1, dist);
        
        int del = minDist(w1, w2, s1+1, s2, dist+1);
        int rep = minDist(w1, w2, s1+1, s2+1, dist+1);
        int ins = minDist(w1, w2, s1, s2+1, dist+1);
        
        int min = del < rep ? del : rep;
        min = ins < min ? ins : min;
        return min;
    }
}
